home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 333_02 / regex1.c < prev    next >
C/C++ Source or Header  |  1989-04-21  |  19KB  |  719 lines
  1. /* Extended regular expression matching and search.
  2.    Copyright (C) 1985 Free Software Foundation, Inc.
  3. */
  4.  
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8. #include "awk.h"
  9.  
  10. /* To test, compile with -Dtest.  This Dtestable feature turns this into   */
  11. /* a self-contained program which reads a pattern, describes how it       */
  12. /* compiles, then reads a string and searches for it.               */
  13.  
  14.  
  15. STATIC VOID     NEAR PASCAL    init_syntax_once(void);
  16. STATIC VOID     NEAR PASCAL    store_jump(char *from, char opcode, char *to);
  17. STATIC VOID     NEAR PASCAL    insert_jump(char op, char *from,
  18.                         char *to, char *current_end);
  19.  
  20.  
  21.  
  22. /* JF this var has taken on whole new meanings as time goes by.  Various   */
  23. /* bits in this int tell how certain pieces of syntax should work       */
  24.  
  25. static int         obscure_syntax = 0;
  26.  
  27.  
  28. /*  Define the syntax stuff, so we can do the \<...\> things.  */
  29.  
  30.  
  31. STATIC VOID NEAR PASCAL init_syntax_once(void)
  32. {
  33.     register int       c;
  34.     static   BOOL      done = FALSE;
  35.  
  36.     if (!done)
  37.     {
  38.     memset(re_syntax_table, 0, sizeof(re_syntax_table));
  39.     for (c = 'a'; c <= 'z'; c++)
  40.         re_syntax_table[c] = Sword;
  41.     for (c = 'A'; c <= 'Z'; c++)
  42.         re_syntax_table[c] = Sword;
  43.     for (c = '0'; c <= '9'; c++)
  44.         re_syntax_table[c] = Sword;
  45.     done = TRUE;
  46.     }
  47.     return;
  48. }
  49.  
  50.  
  51.  
  52. /* compile_pattern takes a regular-expression descriptor string in the        */
  53. /* user's format and converts it into a buffer full of byte commands for    */
  54. /* matching.                                    */
  55. /*                                        */
  56. /*  pattern   is the address of the pattern string                */
  57. /*  size      is the length of it.                        */
  58. /*  bufp      is a  struct re_pattern_buffer *    which points to the info    */
  59. /*          on where to store the byte commands.                */
  60. /*          This structure contains a  char *  which points to the        */
  61. /*          actual space, which should have been obtained with malloc.    */
  62. /*          compile_pattern may use  realloc    to grow the buffer space.   */
  63. /*                                        */
  64. /* The number of bytes of commands can be found out by looking in the        */
  65. /* struct re_pattern_buffer that bufp pointed to, after compile_pattern     */
  66. /* returns.                                    */
  67.  
  68. #define PATPUSH(ch)        (*b++ = (char) (ch))
  69.  
  70. #define PATFETCH(c) \
  71.  {if (p == pend) goto end_of_pattern; \
  72.   c = * (unsigned char *) p++; }
  73.  
  74. #define PATFETCH_RAW(c) \
  75.  {if (p == pend) goto end_of_pattern; \
  76.   c = * (unsigned char *) p++; }
  77.  
  78. #define PATUNFETCH           p--
  79.  
  80. #define EXTEND_BUFFER \
  81.   { char *old_buffer = bufp->buffer; \
  82.     if (bufp->allocated == (1<<16)) goto too_big; \
  83.     bufp->allocated *= 2; \
  84.     if (bufp->allocated > (1<<16)) bufp->allocated = (1<<16); \
  85.     if (!(bufp->buffer = (char *) realloc (bufp->buffer, bufp->allocated))) \
  86.       goto memory_exhausted; \
  87.     c = bufp->buffer - old_buffer; \
  88.     b += c; \
  89.     if (fixup_jump) fixup_jump += c; \
  90.     if (laststart) laststart += c; \
  91.     begalt += c; \
  92.     if (pending_exact) pending_exact += c; \
  93.   }
  94.  
  95.  
  96. /* JF this function is used to compile UN*X style regexps.  In particular,  */
  97. /* ( ) and | don't have to be \ed to have a special meaning                 */
  98.  
  99. int PASCAL re_set_syntax(int syntax)
  100. {
  101.     auto     int    ret;
  102.  
  103.     ret        = obscure_syntax;
  104.     obscure_syntax = syntax;
  105.     return(ret);
  106. }
  107.  
  108.  
  109. char * PASCAL re_compile_pattern(char *pattern, int size, REPAT_BUFFER *bufp)
  110. {
  111.     register char         *b    = bufp->buffer;
  112.     register char         *p    = pattern;
  113.     auto     char         *pend = pattern + size;
  114.     register unsigned          c, c1;
  115.     auto     char         *p1;
  116.  
  117.     /* address of the count-byte of the most recently inserted "exactn"  */
  118.     /* command. This makes it possible to tell whether a new exact-match */
  119.     /* character can be added to that command or requires a new "exactn" */
  120.     /* command.                              */
  121.     auto     char         *pending_exact = 0;
  122.  
  123.     /* address of the place where a forward-jump should go to the end of the */
  124.     /* containing expression. Each alternative of an "or", except the last,  */
  125.     /* ends with a forward-jump of this sort.                     */
  126.     auto     char         *fixup_jump = 0;
  127.  
  128.     /* address of start of the most recently finished expression. This tells */
  129.     /* postfix * where to find the start of its operand.             */
  130.     auto     char        *laststart = 0;
  131.  
  132.     /* In processing a repeat, TRUE means zero matches is allowed */
  133.     auto     BOOL         zero_times_ok;
  134.  
  135.     /* In processing a repeat, TRUE means many matches is allowed */
  136.     auto     BOOL         many_times_ok;
  137.  
  138.     /* address of beginning of regexp, or inside of last \( */
  139.     auto     char        *begalt = b;
  140.  
  141.     /* Stack of information saved by \( and restored by \). Four stack        */
  142.     /* elements are pushed by each \(: First, the value of b. Second, the   */
  143.     /* value of fixup_jump. Third, the value of regnum. Fourth, the value of*/
  144.     /* begalt.                                    */
  145.     auto     int         stackb[40];
  146.     auto     int        *stackp = stackb;
  147.     auto     int        *stacke = stackb + 40;
  148.     auto     int        *stackt;
  149.  
  150.     /* Counts \('s as they are encountered.  Remembered for the matching \), */
  151.     /* where it becomes the "register number" to put in the stop_memory      */
  152.     /* command                                     */
  153.     auto     int         regnum = 1;
  154.  
  155.     bufp->fastmap_accurate = 0;
  156.     init_syntax_once();
  157.  
  158.     if (bufp->allocated == 0)
  159.     {
  160.     bufp->allocated = 28;
  161.     if (bufp->buffer)
  162.         /* EXTEND_BUFFER loses when bufp->allocated is 0 */
  163.         bufp->buffer = (char *) realloc(bufp->buffer, 28);
  164.     else
  165.         /* Caller did not allocate a buffer.  Do it for him */
  166.         bufp->buffer = (char *) malloc(28);
  167.     if (!bufp->buffer)
  168.         goto memory_exhausted;
  169.     begalt = b = bufp->buffer;
  170.     }
  171.  
  172.     while (p != pend)
  173.     {
  174.     if (b - bufp->buffer > bufp->allocated - 10)
  175.         EXTEND_BUFFER;       /* Note that EXTEND_BUFFER clobbers c */
  176.  
  177.     PATFETCH(c);
  178.  
  179.     switch (c)
  180.     {
  181.         case '$':
  182.         /* $ means succeed if at end of line, but only in special  */
  183.         /* contexts. If randomly in the middle of a pattern, it is */
  184.         /* a normal character.                       */
  185.         if (p == pend || (*p == '\\' && (p[1] == ')' || p[1] == '|')))
  186.         {
  187.             PATPUSH(RECODE_ENDLINE);
  188.             break;
  189.         }
  190.         goto normal_char;
  191.         case '^':
  192.         /* ^ means succeed if at beg of line, but only if no       */
  193.         /* preceding pattern.                       */
  194.         if (laststart)
  195.             goto normal_char;
  196.         PATPUSH(RECODE_BEGLINE);
  197.         break;
  198.         case '*':
  199.         case '+':
  200.         case '?':
  201.         /* If there is no previous pattern, char not special.      */
  202.         if (!laststart)
  203.             goto normal_char;
  204.         /* If there is a sequence of repetition chars, collapse it
  205.          * down to equivalent to just one.  */
  206.         zero_times_ok = FALSE;
  207.         many_times_ok = FALSE;
  208.         while (TRUE)
  209.         {
  210.             zero_times_ok |= (c != '+');
  211.             many_times_ok |= (c != '?');
  212.             if (p == pend)
  213.             break;
  214.             PATFETCH(c);
  215.             if (!(c == '*' || c == '+' || c == '?'))
  216.             {
  217.             PATUNFETCH;
  218.             break;
  219.             }
  220.         }
  221.  
  222.         /* Now we know whether 0 matches is allowed, and whether 2 or
  223.          * more matches is allowed.  */
  224.         if (many_times_ok)
  225.         {
  226.             /* If more than one repetition is allowed, put in a
  227.              * backward jump at the end.  */
  228.             store_jump(b, RECODE_MAYBE_FINALIZE_JUMP, laststart - 3);
  229.             b += 3;
  230.         }
  231.         insert_jump(RECODE_ON_FAILURE_JUMP, laststart, b + 3, b);
  232.         pending_exact = 0;
  233.         b += 3;
  234.         if (!zero_times_ok)
  235.         {
  236.             /* At least one repetition required: insert before the
  237.              * loop a skip over the initial on-failure-jump
  238.              * instruction */
  239.             insert_jump(RECODE_DUMMY_FAILURE_JUMP, laststart,
  240.                 laststart + 6, b);
  241.             b += 3;
  242.         }
  243.         break;
  244.  
  245.         case '.':
  246.         laststart = b;
  247.         PATPUSH(RECODE_ANYCHAR);
  248.         break;
  249.  
  250.         case '[':
  251.         if (b - bufp->buffer
  252.             > bufp->allocated - 3 - (1 << BYTEWIDTH) / BYTEWIDTH)
  253.             /* Note that EXTEND_BUFFER clobbers c */
  254.             EXTEND_BUFFER;
  255.  
  256.         laststart = b;
  257.         if (*p == '^')
  258.         {
  259.             PATPUSH(RECODE_CHARSET_NOT);
  260.             ++p;
  261.         }
  262.         else
  263.             PATPUSH(RECODE_CHARSET);
  264.         p1 = p;
  265.  
  266.         PATPUSH((1 << BYTEWIDTH) / BYTEWIDTH);
  267.